package algorthm.systemTraning.heap;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Random;

/**
 * @className: HeapSort
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/29 16:41
 */
public class HeapSort {
    private static Logger logger = LoggerFactory.getLogger(HeapSort.class);
    public static void sort(int[] array){
        if(null == array && array.length < 2){
            return ;
        }
        // 1.弄一个大根堆
        int heapSize = 0 ;
        while(heapSize <= array.length -1){
            insertHeap(array ,heapSize++);
        }
        // 2. 将堆头和堆的最后一个元素交换，并调整大根堆的
        int tail = heapSize - 1 ;
        while(tail > 0){
            heapfy(array , tail--);
        }
    }
    public static void heapfy(int[] heap , int heapSize){
        int root = 0 ;
        int left = 2*root + 1 ;
        int max = 0 ;
        swap(heap , root , heapSize);
        while(left < heapSize){
           max = (left + 1 < heapSize && heap[left + 1] > heap[left])?left + 1: left;
           max = heap[max] > heap[root]?max : root ;
           if(max == root){
               break ;
           }
           swap(heap , root , max);
           root = max ;
           left = root*2 + 1 ;
        }


    }
    public static void insertHeap(int[] heap , int heapSize){
        int root  = (heapSize - 1)/2 ;
        int leaf = heapSize ;
        while(leaf > 0){
            if(heap[root] < heap[leaf]){
                swap(heap , root , leaf);
                leaf = root ;
                root = (leaf - 1)/2;
            }else{
                break ;
            }
        }
    }

    public static void swap(int[] array, int from , int to){
        if(from == to){
             return ;
        }
        array[from] = array[from]^array[to];
        array[to] = array[from]^array[to];
        array[from] = array[from]^array[to];
    }
    public static int[] randomArray(int range , int size){
        Random r = new Random();
        int s = r.nextInt(size) + 1;
        int[] ans = new int[s];
        for(int i = 0 ; i < s ; i++){
            ans[i] = r.nextInt(range);
        }
        return ans ;
    }
    public static int[] copyOf(int[] array){
        int[] ans = new int[array.length];
        for(int i = 0 ; i < array.length ; i++){
            ans[i] = array[i];
        }
        return ans ;
    }
    public static void compare(int range , int size , int times){
        int[] array = null ;
        int[] array2 = null ;
        int[] arrayBackup = null ;
        for(int i = 0 ; i < times ; i++){
           array = randomArray(range , size);
           array2 = copyOf(array);
           arrayBackup = copyOf(array);
           Arrays.sort(array);
           sort(array2);
           if(!Arrays.equals(array , array2)){
                System.out.println("Oops , array is:" + Arrays.toString(arrayBackup));
           }
        }

    }
    public static void main(String[] args){
//        int[] array = {12 , 23 , 11 , 121 , 10 };
//        int[] array = {54, 11, 98, 21, 5, 4, 77};
//        sort(array);
//        System.out.println("array: " + Arrays.toString(array));
        compare(100 , 34 , 1213231);
    }
}
